Ông sinh năm 1925, xóm 4, Nga Điền, Nga Sơn tỉnh Thanh Hóa, Việt Nam, xuất thân từ một gia đình Công giáo. Thời trẻ, ông học ở Tiểu Chủng viện Thanh Hóa. Năm 1943, ông ra Hà Nội thi Tú tài I và theo học một khóa triết học ngắn hạn ở một đại chủng viện. Sau khi tốt nghiệp tú tài, ông về Thanh Hóa dạy học trong một trường dòng.

Năm 1946, khi còn là học sinh, Tuyến biết đến gia đình họ Ngô một cách tình cờ. Người cố vấn tương lai của ông, Ngô Đình Nhu muốn đi từ Hà Nội đến một khu vực Công giáo gần biên giới với Lào và cần một người hướng dẫn. Một linh mục Công giáo đã yêu cầu Tuyến dẫn đường trên một chiếc xe đạp trong khi Nhu đi theo trong một chiếc xích lô có mái che để trốn tránh sự chú ý của thực dân Pháp và Việt Minh.[3]

Năm 1949, ông lên Hà Nội ghi danh vào học cả hai trường Luật và Y Khoa của Viện Đại học Đông Dương. Ông tốt nghiệp ngành Luật năm 1952. Về trường Y thì chưa học xong thì có lệnh động viên ông cùng với 6 sinh viên khác được chuyển sang trường Quân y và ông cũng tốt nghiệp khóa đầu tiên vào năm 1954 với cấp bậc trung úy (tương đương y sĩ). Một số người cho rằng vì việc này đã gây ra sự ngô nhận về chức danh "bác sĩ" của ông, vì thực sự ông chưa tốt nghiệp Đại học Y khoa chính thức và cũng chưa hành nghề y bao giờ.